
#if 0
#include<vector>


using namespace std;

namespace Wang
{


void test01()
{
    stack<int> st;
    for(int i = 0; i < 5; i++) st.push(i);
    while(!st.empty())
    {
        cout << st.top() << " ";
        st.pop();
    }
}

} // namespace Wang

void test_heap()
{
    int a[] = {3,2,5,8,6,7,10};
    // priority_queue<int> h(a, a + sizeof(a) / sizeof(int), greater<int>()); // err
    priority_queue<int> h(a, a + sizeof(a) / sizeof(int)); // 都是int*
    
    while(!h.empty())
    {
        cout << h.top() << ' ';
        h.pop();
    }
}

class A
{
    int _a[10];
public:
    template<class Iterator>
    A(Iterator begin, Iterator end)
    {
        int i = 0;
        while(begin != end)
        {
            _a[i] = *begin;
            i++;
            ++begin;
        }
    }
};

void test02()
{
    int a[] = {3,2,5,8,6,7,10};
    A aa(a, a + sizeof(a) / sizeof(int));
    auto i = a;
    auto j = a + sizeof(a) / sizeof(int);
}
#include<stack>

// 栈是后进先出
// 栈可以存放一系列数据，但向其中增删有一定的限制，只能尾插/尾删
void test_stack()
{
    stack<int> st1;
    st1.push(1);    // 插入元素1，即尾插1
    st1.pop();      // 删除栈顶元素，即尾删
    cout << st1.top() << endl;      // 返回栈顶，即最后一个元素
    cout << st1.empty() << endl;    // 栈为空返回true, 否则返回false
    cout << st1.size() << endl;     // 返回栈里元素的个数
}

void test_queue()
{
    queue<int> q;
    q.push(1);    // 插入元素1，即尾插1
    q.push(2);
    q.pop();      // 删除队头元素，即头删
    cout << q.front() << endl;    // 返回队头元素
    cout << q.back() << endl;     // 返回队尾元素
    cout << q.empty() << endl;    // 队列为空返回true, 否则返回false
    cout << q.size() << endl;     // 返回队列里元素的个数
}

void test_priority_queue()
{
    priority_queue<int> h1;     // 默认是大堆
    priority_queue<int, vector<int>, greater<int>> h2;  // 小堆需要这样写。第一个模板参数表示数据类型，第二个表示底层用vector容器实现，第三个是
    h1.push(1);    // 插入元素1
    h1.push(2);
    h1.pop();      // 删除堆顶元素
    cout << h1.top() << endl;      // 返回堆顶
    cout << h1.empty() << endl;    // 堆为空返回true, 否则返回false
    cout << h1.size() << endl;     // 返回堆里元素的个数
}

#endif

#include"heap.h"

namespace Wang
{
void test01()
{
    stack<int> st;  // 底层容器为vector
    for(int i = 0; i < 5; i++) st.push(i);
    while(!st.empty())
    {
        cout << st.top() << ' ';
        st.pop();
    }
    cout << endl;
    
    stack<int, list<int>> st1;  // 底层容器为list
    for(int i = 0; i < 5; i++) st1.push(i * 10);
    while(!st1.empty())
    {
        cout << st1.top() << ' ';
        st1.pop();
    }
}

void test02()
{
    deque<int> q;
    q.push_back(1);     // 尾插 {1}
    q.push_back(2);     // 尾插 {1,2}
    q.push_front(9);    // 头插 {9,1,2}
    q.push_front(8);    // 头插 {8,9,1,2}
    
    for(int i = 0; i < q.size(); i++)
        cout << q[i] << ' ';    // 支持下标访问
    cout << endl;

    cout << q.front() << endl;  // 相当于q[0]
    cout << q.back() << endl;   // 相当于q[q.size() - 1]
    cout << q.empty() << endl;  // 为空返回true，否则返回false
}

void test03()
{
    queue<int> q1;  // 底层容器为deque
    for(int i = 0; i < 5; i++) q1.push(i);
    while(!q1.empty())
    {
        cout << q1.front() << ' ';
        q1.pop();
    }
    cout << endl;
    
    queue<int, list<int>> q2;  // 底层容器为list
    for(int i = 0; i < 5; i++) q2.push(i * 10);
    while(!q2.empty())
    {
        cout << q2.front() << ' ';
        q2.pop();
    }
}

void test04()
{
    priority_queue<int> h1;     // 默认是大堆
    vector<int> v = { 5,3,1,7,9,4,6,5,10,7 };
    for(auto& e : v)
        h1.push(e);

    // 支持迭代器区间构造, 这样建堆时间复杂度O(n)。上面通过push建堆时间复杂度O(nlogn)
    priority_queue<int> hh1(v.begin(), v.end());

    while(!h1.empty())
    {
        cout << h1.top() << ' ';
        h1.pop();
    }
    cout << endl;

    priority_queue<int, vector<int>, greater<int>> h2;  // 小堆
    for(auto& e : v)
        h2.push(e);
    while(!h2.empty())
    {
        cout << h2.top() << ' ';
        h2.pop();
    }
}

void test05()
{
    priority_queue<int> h;
    int a[10] = { 1,2,3,4,5,6,7,8,9,10 };
    for(auto e : a) 
        h.push(e);
    while(!h.empty())
    {
        cout << h.top() << ' ';
        h.pop();
    }
}

void test06()
{
    priority_queue<int, vector<int>, mygreater<int>> h;
    priority_queue<int> h2;
    int a[10] = { 1,11,3,2,8,9,10,5,22,7 };
    for(auto e : a) 
    {
        h.push(e);
        h2.push(e);
    }

    while(!h.empty())
    {
        cout << h.top() << ' ';
        h.pop();
    }
    cout << endl;

    while(!h2.empty())
    {
        cout << h2.top() << ' ';
        h2.pop();
    }
}

struct Less
{
    // a < b返回true，否则返回false
    bool operator()(int a, int b) const
    {
        return a < b;
    }
};
struct Greater
{
    // a > b返回true，否则返回false
    bool operator()(int a, int b) const
    {
        return a > b;
    }
};

void test07()
{
    Less le;
    Greater gr;
    int a = 10, b = 4;
    if(a < b) 
        cout << "a < b" << endl;
    if(le(a, b))  // 相当于le.operator()(a, b)
        cout << "a < b" << endl;

    if(a > b) 
        cout << "a > b" << endl;
    if(gr(a, b))  // 相当于gr.operator()(a, b)
        cout << "a > b" << endl;
}
}   // namespace Wang


int main()
{
    // Wang::test07();
    priority_queue<int> h1;
    priority_queue<int> h2 = h1;

    return 0;
}


// deque模拟实现：两个vector<int*>，一个用于push_back()，一个用于pop_back(); 



// void test01()
// {
//     priority_queue<int> h1;     // 默认是大堆
//     h1.push(1);    // 插入元素1
//     h1.push(55);
//     h1.push(9);
//     h1.push(13);
//     h1.push(28);
//     cout << h1.top() << endl;      // 返回堆顶，由于是大堆，堆顶元素是55
//     h1.pop();      // 删除堆顶元素
//     h1.empty();    // 堆为空返回true, 否则返回false
//     h1.size();     // 返回堆里元素的个数
// }


// vector<int> a; // 数组模拟堆
// void up(int i)
// {
//     // 到根节点了，停止
//     if(i == 0) return;
//     int p = (i - 1) / 2;
//     if(a[i] > a[p]) // 该节点权值 > 父节点，交换，然后继续向上调整
//     {
//         swap(a[i], a[p]);
//         up(p);
//     }
// }

// void push(int x)
// {
//     a.push_back(x);
//     up(a.size() - 1);
// }

// void down(int p)
// {
//     // 找p的权值最大的儿子节点
//     int s = 2*p + 1;
//     if(s >= a.size()) return;   
//     if(s + 1 < a.size() && a[s + 1] > a[s]) s++;

//     // 权值最大的儿子节点的权值 > 父节点，交换，然后继续向下调整
//     if(a[s] > a[p]) 
//     {
//         swap(a[s], a[p]);
//         down(s);
//     }
// }

// void pop()
// {
//     swap(a[0], a[a.size() - 1]);
//     a.pop_back();
//     down(0);
// }

// int top() { return a[0]; }

// int main()
// {
//     a = { 5,2,8,1,4 };
//     // for(int i = a.size() - 1; i >= 0; i--)
//     // for(int i = (a.size() - 1 - 1) / 2; i >= 0; i--)
//     //     down(i);
    
//     while(!a.empty())
//     {
//         cout << top() << ' ';
//         pop();
//     }
//     return 0;
// }
